import numpy as np
import pandas as pd
import networkx as nx
import re

# 知识点名称列表
nodes = [
    "选择1", "选择2", "选择3", "选择4", "选择5", "选择6", "选择7", "选择8", "选择9", "选择10",
    "填空1", "填空2", "填空3", "填空4", "填空5", "填空6",
    "计算1", "计算2", "证明1", "证明2", "综合应用1", "综合应用2"
]

# 读取相关系数
corr_dict = {}
with open('相关系数.txt', 'r', encoding='utf-8') as f:
    for line in f:
        match = re.match(r"r\\((.+),(.+)\\) = ([\\d\\.-]+)", line.strip())
        if match:
            a, b, r = match.groups()
            corr_dict[(a.strip(), b.strip())] = float(r)
            corr_dict[(b.strip(), a.strip())] = float(r)  # 相关系数对称

# 读取邻接矩阵
df = pd.read_excel('试卷知识点关联规则汇总.xls', header=None)
df.index = nodes
df.columns = nodes
matrix = df.values.copy()

# 构建有向图
g = nx.DiGraph()
g.add_nodes_from(nodes)
for i, row in enumerate(matrix):
    for j, val in enumerate(row):
        if val == 1:
            g.add_edge(nodes[i], nodes[j])

edges_to_remove = set()
while True:
    cycles = list(nx.simple_cycles(g))
    if not cycles:
        break
    for cycle in cycles:
        # 找出环中相关系数最小的边
        min_r = float('inf')
        min_edge = None
        for i in range(len(cycle)):
            a = cycle[i]
            b = cycle[(i+1)%len(cycle)]
            r = corr_dict.get((a, b), 0)  # 若无相关系数，视为0
            if r < min_r:
                min_r = r
                min_edge = (a, b)
        if min_edge and g.has_edge(*min_edge):
            g.remove_edge(*min_edge)
            i = nodes.index(min_edge[0])
            j = nodes.index(min_edge[1])
            matrix[i, j] = 0
            edges_to_remove.add(min_edge)

# 检查是否已无环
if nx.is_directed_acyclic_graph(g):
    print("已去环，可用于拓扑排序。")
else:
    print("仍有环路，请人工干预。")

# 输出去环后的邻接矩阵到新Excel文件
df_new = pd.DataFrame(matrix, index=nodes, columns=nodes)
df_new.to_excel('去环邻接矩阵.xlsx')

# 同时输出被打断的边
with open('removed_edges.txt', 'w', encoding='utf-8') as f:
    f.write("被打断的边（已删除）：\n")
    for edge in edges_to_remove:
        f.write(f"{edge[0]} -> {edge[1]}\n")
